package com.zklh.leetcode.other.problem31;

public class Solution {
    public void nextPermutation(int[] nums) {
        // 是否存在比当前数组排列更大的排列
        boolean isHasBigger = false;
        for (int i = nums.length-1; i > 0; i--) {
            // 如果当前位置的元素,比前一个元素大, 则需要更换前一个元素
            if(nums[i] > nums[i-1]){
                /*寻找和前一个元素更换的位置, 需要找到当前元素向后的某一个元素比当前元素大,
                但是下一个元素比当前元素小(因为当前元素的后面的数都小于等于当前元素)*/
                // 要和i-1交换的位置
                int swapIndex = i;
                while( swapIndex+1 < nums.length){
                    // 如果当前位置的数比i-1的数大, 当前位置右边的数比i-1小则当前位置的数可以与i-1位置互换
                    if(nums[swapIndex] > nums[i-1] && nums[swapIndex+1] <= nums[i-1]){
                        break;
                    }
                    swapIndex++;
                }
                swap(nums,i-1,swapIndex);
                // 互换之后, 需要对当前位置后的所有数变为最小, 也就是对后的所有数进行升序排列
                reverse(nums,i,nums.length-1);
                isHasBigger = true;
                break;
            }
        }
        if(!isHasBigger){
            reverse(nums,0,nums.length-1);
        }
    }


    /**
     * 对数组,指定其左右边界,进行翻转
     * @param nums
     * @param left
     * @param right
     */
    private void reverse(int[] nums, int left, int right){
        while(left < right){
            swap(nums,left++,right--);
        }
    }

    /**
     * 对指定的左右索引进行值互换
     * @param nums
     * @param left
     * @param right
     */
    private void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public static void main(String[] args){

        int[] nums = {2,3,4,1,3,2};
        Solution solution = new Solution();
        solution.nextPermutation(nums);
        System.out.println("坐看落花");
    }
}
